{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from math import log"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>humility</th>\n",
       "      <th>outlook</th>\n",
       "      <th>play</th>\n",
       "      <th>temp</th>\n",
       "      <th>windy</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>high</td>\n",
       "      <td>sunny</td>\n",
       "      <td>no</td>\n",
       "      <td>hot</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>high</td>\n",
       "      <td>sunny</td>\n",
       "      <td>no</td>\n",
       "      <td>hot</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>high</td>\n",
       "      <td>overcast</td>\n",
       "      <td>yes</td>\n",
       "      <td>hot</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>high</td>\n",
       "      <td>rainy</td>\n",
       "      <td>yes</td>\n",
       "      <td>mild</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>normal</td>\n",
       "      <td>rainy</td>\n",
       "      <td>yes</td>\n",
       "      <td>cool</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>normal</td>\n",
       "      <td>rainy</td>\n",
       "      <td>no</td>\n",
       "      <td>cool</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>normal</td>\n",
       "      <td>overcast</td>\n",
       "      <td>yes</td>\n",
       "      <td>cool</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>high</td>\n",
       "      <td>sunny</td>\n",
       "      <td>no</td>\n",
       "      <td>mild</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>normal</td>\n",
       "      <td>sunny</td>\n",
       "      <td>yes</td>\n",
       "      <td>cool</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>normal</td>\n",
       "      <td>rainy</td>\n",
       "      <td>yes</td>\n",
       "      <td>mild</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>normal</td>\n",
       "      <td>sunny</td>\n",
       "      <td>yes</td>\n",
       "      <td>mild</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>high</td>\n",
       "      <td>overcast</td>\n",
       "      <td>yes</td>\n",
       "      <td>mild</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>normal</td>\n",
       "      <td>overcast</td>\n",
       "      <td>yes</td>\n",
       "      <td>hot</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>high</td>\n",
       "      <td>rainy</td>\n",
       "      <td>no</td>\n",
       "      <td>mild</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   humility   outlook play  temp  windy\n",
       "0      high     sunny   no   hot  False\n",
       "1      high     sunny   no   hot   True\n",
       "2      high  overcast  yes   hot  False\n",
       "3      high     rainy  yes  mild  False\n",
       "4    normal     rainy  yes  cool  False\n",
       "5    normal     rainy   no  cool   True\n",
       "6    normal  overcast  yes  cool   True\n",
       "7      high     sunny   no  mild  False\n",
       "8    normal     sunny  yes  cool  False\n",
       "9    normal     rainy  yes  mild  False\n",
       "10   normal     sunny  yes  mild   True\n",
       "11     high  overcast  yes  mild   True\n",
       "12   normal  overcast  yes   hot  False\n",
       "13     high     rainy   no  mild   True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df = pd.read_csv('./example_data.csv')\n",
    "df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def entropy(ele):\n",
    "    '''\n",
    "    function: Calculating entropy value.\n",
    "    input: A list contain categorical value.\n",
    "    output: Entropy value.\n",
    "    entropy = - sum(p * log(p)), p is a prob value.\n",
    "    '''\n",
    "    # Calculating the probability distribution of list value\n",
    "    probs = [ele.count(i)/len(ele) for i in set(ele)]\n",
    "    # Calculating entropy value\n",
    "    entropy = -sum([prob*log(prob, 2) for prob in probs])\n",
    "    return entropy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9402859586706309"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "entropy(df['play'].tolist())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def split_dataframe(data, col):\n",
    "    '''\n",
    "    function: split pandas dataframe to sub-df based on data and column.\n",
    "    input: dataframe, column name.\n",
    "    output: a dict of splited dataframe.\n",
    "    '''\n",
    "    # unique value of column\n",
    "    unique_values = data[col].unique()\n",
    "    # empty dict of dataframe\n",
    "    result_dict = {elem : pd.DataFrame for elem in unique_values}\n",
    "    # split dataframe based on column value\n",
    "    for key in result_dict.keys():\n",
    "        result_dict[key] = data[:][data[col] == key]\n",
    "    return result_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'cool':   humility   outlook play  temp  windy\n",
       " 4   normal     rainy  yes  cool  false\n",
       " 5   normal     rainy   no  cool   true\n",
       " 6   normal  overcast  yes  cool   true\n",
       " 8   normal     sunny  yes  cool  false,\n",
       " 'hot':    humility   outlook play temp  windy\n",
       " 0      high     sunny   no  hot  false\n",
       " 1      high     sunny   no  hot   true\n",
       " 2      high  overcast  yes  hot  false\n",
       " 12   normal  overcast  yes  hot  false,\n",
       " 'mild':    humility   outlook play  temp  windy\n",
       " 3      high     rainy  yes  mild  false\n",
       " 7      high     sunny   no  mild  false\n",
       " 9    normal     rainy  yes  mild  false\n",
       " 10   normal     sunny  yes  mild   true\n",
       " 11     high  overcast  yes  mild   true\n",
       " 13     high     rainy   no  mild   true}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "split_example = split_dataframe(df, 'temp')\n",
    "split_example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hot    humility   outlook play temp  windy\n",
      "0      high     sunny   no  hot  false\n",
      "1      high     sunny   no  hot   true\n",
      "2      high  overcast  yes  hot  false\n",
      "12   normal  overcast  yes  hot  false\n",
      "mild    humility   outlook play  temp  windy\n",
      "3      high     rainy  yes  mild  false\n",
      "7      high     sunny   no  mild  false\n",
      "9    normal     rainy  yes  mild  false\n",
      "10   normal     sunny  yes  mild   true\n",
      "11     high  overcast  yes  mild   true\n",
      "13     high     rainy   no  mild   true\n",
      "cool   humility   outlook play  temp  windy\n",
      "4   normal     rainy  yes  cool  false\n",
      "5   normal     rainy   no  cool   true\n",
      "6   normal  overcast  yes  cool   true\n",
      "8   normal     sunny  yes  cool  false\n"
     ]
    }
   ],
   "source": [
    "for item, value in split_example.items():\n",
    "    print(item, value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.2467498197744391,\n",
       " 'outlook',\n",
       " {'overcast':    humility   outlook play  temp  windy\n",
       "  2      high  overcast  yes   hot  false\n",
       "  6    normal  overcast  yes  cool   true\n",
       "  11     high  overcast  yes  mild   true\n",
       "  12   normal  overcast  yes   hot  false,\n",
       "  'rainy':    humility outlook play  temp  windy\n",
       "  3      high   rainy  yes  mild  false\n",
       "  4    normal   rainy  yes  cool  false\n",
       "  5    normal   rainy   no  cool   true\n",
       "  9    normal   rainy  yes  mild  false\n",
       "  13     high   rainy   no  mild   true,\n",
       "  'sunny':    humility outlook play  temp  windy\n",
       "  0      high   sunny   no   hot  false\n",
       "  1      high   sunny   no   hot   true\n",
       "  7      high   sunny   no  mild  false\n",
       "  8    normal   sunny  yes  cool  false\n",
       "  10   normal   sunny  yes  mild   true})"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def choose_best_col(df, label):\n",
    "    '''\n",
    "    funtion: choose the best column based on infomation gain.\n",
    "    input: datafram, label\n",
    "    output: max infomation gain, best column, \n",
    "            splited dataframe dict based on best column.\n",
    "    '''\n",
    "    # Calculating label's entropy\n",
    "    entropy_D = entropy(df[label].tolist())\n",
    "    # columns list except label\n",
    "    cols = [col for col in df.columns if col not in [label]]\n",
    "    # initialize the max infomation gain, best column and best splited dict\n",
    "    max_value, best_col = -999, None\n",
    "    max_splited = None\n",
    "    # split data based on different column\n",
    "    for col in cols:\n",
    "        splited_set = split_dataframe(df, col)\n",
    "        entropy_DA = 0\n",
    "        for subset_col, subset in splited_set.items():\n",
    "            # calculating splited dataframe label's entropy\n",
    "            entropy_Di = entropy(subset[label].tolist())\n",
    "            # calculating entropy of current feature\n",
    "            entropy_DA += len(subset)/len(df) * entropy_Di\n",
    "        # calculating infomation gain of current feature\n",
    "        info_gain = entropy_D - entropy_DA\n",
    "        \n",
    "        if info_gain > max_value:\n",
    "            max_value, best_col = info_gain, col\n",
    "            max_splited = splited_set\n",
    "    return max_value, best_col, max_splited\n",
    "    \n",
    "choose_best_col(df, 'play')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ID3Tree:\n",
    "    # define a Node class\n",
    "    class Node:\n",
    "        def __init__(self, name):\n",
    "            self.name = name\n",
    "            self.connections = {}\n",
    "\n",
    "        def connect(self, label, node):\n",
    "            self.connections[label] = node\n",
    "            \n",
    "    def __init__(self, data, label):\n",
    "        self.columns = data.columns\n",
    "        self.data = data\n",
    "        self.label = label\n",
    "        self.root = self.Node(\"Root\")\n",
    "    \n",
    "    # print tree method\n",
    "    def print_tree(self, node, tabs):\n",
    "        print(tabs + node.name)\n",
    "        for connection, child_node in node.connections.items():\n",
    "            print(tabs + \"\\t\" + \"(\" + connection + \")\")\n",
    "            self.print_tree(child_node, tabs + \"\\t\\t\")\n",
    "    \n",
    "    def construct_tree(self):\n",
    "        self.construct(self.root, \"\", self.data, self.columns)\n",
    "    \n",
    "    # construct tree\n",
    "    def construct(self, parent_node, parent_connection_label, input_data, columns):\n",
    "        max_value, best_col, max_splited = choose_best_col(input_data[columns], self.label)\n",
    "        \n",
    "        if not best_col:\n",
    "            node = self.Node(input_data[self.label].iloc[0])\n",
    "            parent_node.connect(parent_connection_label, node)\n",
    "            return\n",
    "\n",
    "        node = self.Node(best_col)\n",
    "        parent_node.connect(parent_connection_label, node)\n",
    "        \n",
    "        new_columns = [col for col in columns if col != best_col]\n",
    "        \n",
    "        # Recursively constructing decision trees\n",
    "        for splited_value, splited_data in max_splited.items():\n",
    "            self.construct(node, splited_value, splited_data, new_columns)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Root\n",
      "\t()\n",
      "\t\toutlook\n",
      "\t\t\t(sunny)\n",
      "\t\t\t\thumility\n",
      "\t\t\t\t\t(high)\n",
      "\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t(hot)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(false)\n",
      "\t\t\t\t\t\t\t\t\t\tno\n",
      "\t\t\t\t\t\t\t\t\t(true)\n",
      "\t\t\t\t\t\t\t\t\t\tno\n",
      "\t\t\t\t\t\t\t(mild)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(false)\n",
      "\t\t\t\t\t\t\t\t\t\tno\n",
      "\t\t\t\t\t(normal)\n",
      "\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t(cool)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(false)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t\t\t\t\t(mild)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(true)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t(overcast)\n",
      "\t\t\t\thumility\n",
      "\t\t\t\t\t(high)\n",
      "\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t(hot)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(false)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t\t\t\t\t(mild)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(true)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t\t\t(normal)\n",
      "\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t(cool)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(true)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t\t\t\t\t(hot)\n",
      "\t\t\t\t\t\t\t\twindy\n",
      "\t\t\t\t\t\t\t\t\t(false)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t(rainy)\n",
      "\t\t\t\twindy\n",
      "\t\t\t\t\t(false)\n",
      "\t\t\t\t\t\thumility\n",
      "\t\t\t\t\t\t\t(high)\n",
      "\t\t\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t\t\t(mild)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t\t\t\t\t(normal)\n",
      "\t\t\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t\t\t(cool)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t\t\t\t\t\t\t(mild)\n",
      "\t\t\t\t\t\t\t\t\t\tyes\n",
      "\t\t\t\t\t(true)\n",
      "\t\t\t\t\t\thumility\n",
      "\t\t\t\t\t\t\t(normal)\n",
      "\t\t\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t\t\t(cool)\n",
      "\t\t\t\t\t\t\t\t\t\tno\n",
      "\t\t\t\t\t\t\t(high)\n",
      "\t\t\t\t\t\t\t\ttemp\n",
      "\t\t\t\t\t\t\t\t\t(mild)\n",
      "\t\t\t\t\t\t\t\t\t\tno\n"
     ]
    }
   ],
   "source": [
    "tree1 = ID3Tree(df, 'play')\n",
    "tree1.construct_tree()\n",
    "tree1.print_tree(tree1.root, \"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
